COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\chapter{Writing Recursive Function Definitions}
C00005 00003	\section{Static and dynamic ways of programming.}
C00012 00004	\section{Recursive definition of functions on natural numbers.}
C00034 ENDMK
C⊗;
\chapter{Writing Recursive Function Definitions}
\chaplab{writin}


	In chapter \chapref{readin} we discussed the basic constructs of 
\lisp\ and explained how \lisp\ evaluates terms built up from them.  
The notion of a recursively defined function was introduced and the rules for 
computing the value of such a defined function were given.  
In addition we showed how \lisp\ programs are represented as S-expressions and 
how these programs are interpreted by the function $eval$.   
By now you should be able to read and understand simple \lisp\ programs.  
The next step is learning
to write \lisp\ programs.  In principle you already know all that is necessary;
however, there are some basic ideas and  techniques which are 
useful in solving \lisp\ programming problems.  The purpose of
this chapter is to help you learn to think recursively and to familiarize
you with some of the basic techniques and
standard forms of recursive programs.  The final section contains 
\lisp\ programming problems.


\section{Static and dynamic ways of programming.}
\sectlab{tdvsbu}
	In order to write recursive function definitions, one must
think about programming differently than is customary when writing
programs in languages like PASCAL or ALGOL or machine language.
In these languages, one has in mind the state of the computation as
represented by the values of certain variables or locations in the
memory of the machine, and then one writes statements or machine
instructions in order to make the state change in an appropriate way.
Writing recursive function definitions requires a different approach.
Given a function to define, one asks for what
values of the arguments the value of the function is immediate, and,
given arbitrary values of the arguments, for what simpler
arguments must the function be known in order to give the value of
the function for the given arguments.  

	Consider the numerical function $n!\,$.  For
what argument is the value of the function immediate?  Clearly, for
$n = 0$ or $n = 1$, the value is immediate: it is 1.  Moreover,
we can get the value for an arbitrary $n$ if we know the value for
$n\minus 1$.  Also, we see that the case $n = 1$ 
can be obtained from the $n = 0$ case by the same rule that is
used in the general case.
This leads to the recursive definition:
\beginfundef
\funlab{facti}
n! ← \qif n\qequal 0 \qthen 1 \qelse n\times[n\minus 1]!\,.
\endfundef

	We may regard this as a ``static'' way of looking at programming.
We ask what simpler cases the general case of our function depends on
rather than how we build up the desired state of the computation.

	An example of the dynamic approach to programming is
the following ALGOL 60 program for computing $n!\,$:
\beginfundef
\funlab{factorial}
\vbox{
\ialign{$#$\hfill&$#$\hfill\cr
{\bf integer\ procedure\ }factorial(n); {\bf integer}\ s,i;\hidewidth\cr
{\bf begin}\cr
&s := 1;\cr
&i := n;\cr
loop:&\qif i= 0 \qthen {\bf go\ to\ }  done ;\cr
& s  :=  i \ast s ;\cr
& i  :=  i \minus 1;\cr
&\qgo  loop ;\cr
done:&\,factorial := s ;\cr
{\bf end};\cr
}
}\endfundef
	The recursive style provides a built in mechanism of problem
solving which is rather like what is usually called {\it subgoaling}.  We shall
also see later that it also leads to rather natural methods of proving
statements about programs.

When we discuss the mechanism of
recursion, we will see that the above LISP program for factorial
is inefficient.
The following somewhat longer program is more efficient, and corresponds to the
above ALGOL program rather precisely:
\beginfundef
\funlab{factii}
\vbox{
\hbox{$ n ! ←  fact [ n ,1],$}
\hbox{$ fact [ i , s ] ← \qif  i =0\qthen s \qelse fact [ i \minus 1, i\ast s ].$}
}\endfundef
%
Some \lisp\ systems convert automatically from the clearer recursive form
to the ``iterative'' form in certain cases in which the latter is more efficient.

	Perhaps the distinction between the two styles
is equivalent to what some people call
the distinction between {\it top-down\/} and {\it bottom-up\/} programming.
LISP offers both, but the static style is better developed in LISP than
in other languages, and we will emphasize it.

\section{Recursive definition of functions on natural numbers.}
\sectlab{numrec}

	In the next several sections we examine various forms of recursive
function definition.
We begin by considering recursive definitions of numerical functions.
We have already seen one example, the factorial function.
In general, we give a recursive definition by defining the value of
the function for any argument using values for smaller arguments, and
using a collection of pre-defined, or built-in functions.
Notice that we will have to
specify the value for 0 directly as there are no smaller numbers.
The method of function definition is parallel to the description of the
domain of natural numbers in terms of the number 0 and the operation 
of successor, namely a number is either 0 or obtained 
by applying successor to a previously constructed number.

	Recursive functions of natural numbers have the the subject of much study
by logicians and mathematicians.  One fairly nice result is that any
such function can be computed starting with the constant 0, the
basic functions $\qaddone$ (more commonly known as 
{\it successor}), $\qsubone$ (also known 
as {\it predecessor}), and the tools
for recursive definition described in chapter \chapref{readin}.
(Actually one can get by with even less, but we do not attempt that here.)
For example the sum and difference of two numbers are given by
\beginlisp
(DEFUN %PLUS (N M) 
  (COND ((EQUAL N 0) M) (T (ADD1 (PLUS (SUB1 N) M)))))
;
(DEFUN DIFFER (N M)
  (COND ((EQUAL N 0) 0) ((EQUAL M 0) N) (T (DIFFER (SUB1 N) (SUB1 M))) ))
(bb tex '(%plus differ))
\endlisp
\beginfundef
\funlab{plus}
\funlab{differ}
\xx{0} n + m ← \qif  n \qequal 0 \qthen  m \qelse  \qaddone[[\qsubone n] + m]\cr
\noalign{\medskip}
\xx{0} differ[n, m] ← \cr
\xx{4}     \qif  n \qequal 0 \qthen  0 \qelsif  m \qequal 0 \qthen  n \qelse 
 differ[\qsubone n, \qsubone m]\cr
\endfundef
while the predicate {\it greaterp}, which is true if the first argument is
greater that the second can be computed by
\beginlisp
(DEFUN %GREATERP (N M)
  (COND ((EQUAL N 0) 0) ((EQUAL M 0) 1) (T (GREATERP (SUB1 N) (SUB1 M))) ))
(bb tex `(%greaterp))
\endlisp
\beginfundef
\funlab{greaterp}
\xx{0} greaterp[n, m] ← \cr
\xx{4}     \qif  n \qequal 0 \qthen  0 \qelsif  m \qequal 0 \qthen  1 \qelse 
greaterp[\qsubone n, \qsubone m]\cr
\endfundef

Here we use 0 to represent \qF\ and 1 to represent \qT\ in order to
keep within the domain of numbers.  We also write $n+1$ instead of $\qaddone n$
and $n\minus 1$ instead of $\qsubone n$.

	We could continue along these lines using $+$
to define $\times$,
$\times$ to define {\it expt}, $differ$ to define 
$\div$ and so forth
building up a collection of useful functions.  We will leave this as an exercise
for the reader.  

In the course of building up these definitions, some patterns of definition
are used repeatedly.
Perhaps the simplest such form is expressed by the following schema:
\beginlisp
(DEFUN F(N)
  (COND ((EQUAL N 0) A)
	(T (H (DIFFERENCE N 1) (F1 (DIFFERENCE N 1))))))
(bb tex '(f))
\endlisp
\beginfundef
\funlab{pri}
\xx{0} f n ← \qif  n \qequal 0 \qthen  a \qelse  h[n \minus 1, f[n \minus 
1]]\cr
\endfundef

Here {\it f\/} is defined in terms of a fixed constant {\it a\/} 
and a given function 
{\it h}. 
This corresponds to what logicians call
``primitive recursion without parameters''.  If we
take  $h[k,m]=[k+1] \times m$ and $a = 1$ we have the definition of {\it fact\/}
given above in function \funref{facti}.

If we allow parameters, we get the usual form of
primitive recursion (shown with only one parameter for simplicity)
\beginlisp
(DEFUN F(N M)
  (COND ((EQUAL N 0) (G M))
	(T (H (DIFFERENCE N 1) M (F (DIFFERENCE N 1) M)))))
(bb tex '(f))
\endlisp
\beginfundef
\funlab{prii}
\xx{0} f[n, m] ← \qif  n \qequal 0 \qthen  g m \qelse  h[n \minus 1, m, 
f[n \minus 1, m]]\cr
\endfundef

The definition of $+$ given above has this form with $g[m]=m$ and
$h[n,m,k]=k+1$.   As a further generalization we allow the 
parametric argument of $f$ (in the recursive call)
to be a given function of the parameter and the first argument giving
\beginlisp
(DEFUN F(N M)
  (COND ((EQUAL N 0) (G M))
	(T (H (DIFFERENCE N 1) M (F (DIFFERENCE N 1) (J (DIFFERENCE N 1) M))))))
(bb tex '(f))
\endlisp
\beginfundef
\funlab{priii}
\xx{0} f[n, m] ← \qif  n \qequal 0 \qthen  g m \qelse  h[n \minus 1, m, 
f[n \minus 1, j[n \minus 1, m]]]\cr
\endfundef
The definitions of $differ$ and $greaterp$ given above has this form.  Also the 
alternate recursive definition of the factorial function [\funref{factii}]
is of this form.
We may wish to express the computation directly in terms of several
preceding values instead of just $f[n\minus 1]$.   One form of this
``course of values'' type recursion is given by
\beginfundef
\funlab{priv}
\xx{0} f[n] ← \qif n \qequal 0 \qthen a↓0 \qelse\cr
\xx{4} \qif n \qequal 1 \qthen a↓1 \qelse\cr
\xx{4} \cdots\cr
\xx{4} \qif n \qequal b\qthen a↓b \qelse\cr
\xx{6} h[n,f[p↓1[n]],\ldots,f[p↓c[n]]]\cr
\endfundef
 where $0≤p↓i[n]<n$ for $1≤i≤c$ when $b<n$.  As an example we have the
definition of the function giving the $n$th Fibonacci number.  It is
usually denoted $F↓n$, but we'll use the \lisp\ notation $fib n$ in
our definitions.  We have
\beginlisp
(DEFUN FIB (N)
  (COND ((EQUAL N 0) 0)
	((EQUAL N 1) 1)
	(T (PLUS (FIB (SUB1 N)) (FIB (SUB1 (SUB1 N))))) ))
(bb tex '(fib))
\endlisp
\beginfundef
\funlab{fib}
\xx{0} fib n ← \qif  n \qequal 0 \qthen  0\cr
\xx{8}         \qelsif  n \qequal 1 \qthen  1\cr
\xx{8}         \qelse  fib \qsubone n + fib \qsubone \qsubone n\cr
\endfundef
We note that this is a particularly inefficient definition, as evaluation    
of $fib[n]$ takes $O(fib(n))$ steps.
A more efficient definition is:
\beginlisp
(DEFUN FIBA (N) (FIBB N 0 1))
(DEFUN FIBB (N K M) (COND ((EQUAL N 0) K) (T (FIBB (SUB1 N) M (PLUS K M))) ))
(bb tex '(fiba fibb))
\endlisp
\beginfundef
\funlab{fiba}
\xx{0} fiba n ← fibb[n, 0, 1]\cr
\noalign{\medskip}
\xx{0} fibb[n, k, m] ← \qif  n \qequal 0 \qthen  k \qelse  fibb[\qsubone n, 
m, k + m]\cr
\endfundef
Evaluation of the $n$th Fibonacci number using this definition requires
only order of $n$ amount of work.

	The above improvement in the \lisp\ program for computing Fibonacci
numbers is a ``computer science improvement'' in that
the improved program computes only once what the original program computes
many times.  We can make a further ``mathematical improvement'' by proving
%
$$\left(\matrix{1&1\cr 1&0\cr}\right)↑n =
 \left(\matrix{F↓{n+1}&F↓n\cr F↓n&F↓{n\minus1}\cr}\right)$$
%
by mathematical induction.
To compute $F↓n$ for some large $n$, we express $n$ as
a binary number and compute $\left(\matrix{1&1\cr 0&1\cr}\right)↑n$ by
successive squaring to get the needed $2↑k$th powers and multiply the
powers selected by the non-zero digits of the binary expansion of $n$.
It is easily seen that the number of operations is then proportional
to $log n$.  The moral is that sometimes one can do a lot better than
purely programming considerations suggest by applying appropriate
mathematics.

	The above forms of recursive function definition all have a very nice 
property: assuming that the given functions appearing in the schemas 
are total, the function defined by the schema is total.  That is the rules given for
evaluation of such functions will always produce an answer in a finite number of
steps.  The general form of recursive definition
\beginfundef
\funlab{prec}
f[n↓0,\ldots,n↓k] ← \tau[f,n↓0,\ldots,n↓k]
\endfundef
where $\tau$ is some term involving $f$, the arguments $n↓i$ and perhaps additional
given functions.   Definitions of this general form are not guaranteed to
define total functions.  As an extreme example, the definition
\beginfundef
\funlab{loop}
loop n←loop n
\endfundef
is perfectly acceptable to \lisp, but the rules for computation will
not produce an answer for any value of $n$.  

There are important cases
where the function defined by a recursive definition is total, but where
the definition does not fit any of the above patterns.  
A very well-known example of such a function on natural numbers
is known as Ackermann's function given by
\beginlisp
(DEFUN ACK (M N)
  (COND ((EQUAL M 0) (ADD1 N))
	((EQUAL N 0) (ACK (SUB1 M) 1))
	(T (ACK (SUB1 M) (ACK M (SUB1 N)))) ))
(bb tex '(ack))
\endlisp
\beginfundef
\funlab{ack}
\xx{0} ack[m, n] ← \cr
\xx{4}     \qif  m \qequal 0 \qthen  \qaddone n\cr
\xx{4}     \qelsif  n \qequal 0 \qthen  ack[\qsubone m, 1]\cr
\xx{4}     \qelse  ack[\qsubone m, ack[m, \qsubone n]]\cr
\endfundef

The proof that this function cannot be defined by primitive recursion
is based on showing that $ack[m,n]$ grows faster than any
primitive recursive function.